package P2分治回溯;
//二分查找
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12};
        System.out.println(binarySearch(arr, 11));
        System.out.println(binarySearch(arr, 2));
        System.out.println(binarySearch(arr, 5));
        System.out.println(binarySearch(arr, -1));
        System.out.println(binarySearch(arr, 13));
        System.out.println(binarySearch(arr, 0, arr.length - 1, 11));
        System.out.println(binarySearch(arr, 0, arr.length - 1, 2));
        System.out.println(binarySearch(arr, 0, arr.length - 1, 5));
        System.out.println(binarySearch(arr, 0, arr.length - 1, -1));
        System.out.println(binarySearch(arr, 0, arr.length - 1, 13));
    }

    //O(logN)
    //递归实现
    private static int binarySearch(int[] arr, int low, int high, int key) {
        if (low > high) {
            return -1;
        }
        int mid = (high - low) / 2 + low;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] < key) {
            return binarySearch(arr, mid + 1, high, key);
        } else {
            return binarySearch(arr, low, mid - 1, key);
        }
    }

    //O(logN)
    //迭代实现
    private static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int mid = (high - low) / 2 + low;
        while (arr[mid] != key) {
            if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if (low > high) {
                return -1;
            }
            mid = (high - low) / 2 + low;
        }
        return mid;
    }
}
